// 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
// 解题思路 f（x） = min{f(x-n)+1}  n为硬币面额

function coinChange(coins, amount) {
    if (amount === 0) return 0
    let dp = new Array(amount + 1).fill(Infinity)
    dp[0] = 0
    for (let i = 0; i < dp.length; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (i - coins[j] < 0) {
                continue
            }
            dp[i]=Math.min(dp[i],dp[i-coins[j]]+1)
        }
    }
    if (dp[amount]===Infinity) return  -1
    else return dp[amount]
}
let coins=[2,5,7]
let amout= 27
console.log(coinChange(coins,amout))